// https://leetcode.cn/problems/cousins-in-binary-tree/
// Created by ade on 2022/8/23.
//
#include <iostream>
#include <vector>


using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode() : val(0), left(nullptr), right(nullptr) {}

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    // 同一层，但是父节点不同
    int xIndex = 0, yIndex = 0;
    TreeNode *xP = nullptr;
    TreeNode *yP = nullptr;

    bool isCousins(TreeNode *root, int x, int y) {
        dfs(root, x, y, 0);
        return xIndex > 0 && yIndex > 0 && xIndex == yIndex && xP != yP;
    }

    void dfs(TreeNode *root, int x, int y, int index) {
        if (!root) return;
        if (root->left && root->left->val == x || root->right && root->right->val == x) {
            xP = root;
            xIndex = index;
        }
        if (root->left && root->left->val == y || root->right && root->right->val == y) {
            yP = root;
            yIndex = index;
        }
        dfs(root->left, x, y, index + 1);
        dfs(root->right, x, y, index + 1);
    }
};
